package Text6;

import java.util.Scanner;

public class Main {
    //    维护一个集合，初始时集合为空，支持如下几种操作：
//    I x，插入一个数 x；
//    PM，输出当前集合中的最小值；
//    DM，删除当前集合中的最小值（数据保证此时的最小值唯一）；
//    D k，删除第 k个插入的数；
//    C k x，修改第 k个插入的数，将其变为 x；
//    现在要进行 N次操作，对于所有第 2个操作，输出当前集合的最小值。
//    输入格式
//    第一行包含整数 N。
//    接下来 N行，每行包含一个操作指令，操作指令为 I x，PM，DM，D k 或 C k x 中的一种。
    public static final int N = 100010;
    public static int[] h = new int[N], ph = new int[N], hp = new int[N];
    public static int size, m;


    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        size = 0;
        m = 0;
        while(n -- > 0){
            String s = scanner.next();
            if(s.equals("I")){
                int x= scanner.nextInt();
                size ++;m ++;
                ph[m] = size;hp[size] = m;
                h[size] = x;
                up(size);
            }else if(s.equals("PM")){
                System.out.println(h[1]);
            }else if(s.equals("DM")){
                heap_swap(1,size);
                size--;
                down(1);
            }else if(s.equals("D")){
                int k = scanner.nextInt();
                k = ph[k];
                heap_swap(k,size);
                size--;
                up(k);
                down(k);
            }else{
                int k = scanner.nextInt();
                int x = scanner.nextInt();
                k = ph[k];
                h[k] = x;
                up(k);
                down(k);

            }
        }
    }

    public static void down(int u) {
        int t = u;
        if (2 * u <= size && h[2 * u] < h[t]) {
            t = 2 * u;
        }
        if (2 * u + 1 <= size && h[2 * u + 1] < h[t]) {
            t = 2 * u + 1;
        }
        if(t!=u){
            heap_swap(t,u);
            down(t);
        }
    }

    public static void up(int u) {
    while(u/2>0&&h[u/2]>h[u]){
        heap_swap(u,u/2);
        u/=2;
    }
    }

    public static void heap_swap(int a, int b) {
        swap(ph, hp[a], hp[b]);
        swap(hp, a, b);
        swap(h, a, b);
    }

    public static void swap(int[] arr, int x, int y) {
        int tmp = arr[x];
        arr[x] = arr[y];
        arr[y] = tmp;
    }
}
